FPS24 E - 数列 3

$ \sum_{i=1}^M c_i=N かつ $ c_i \le i であるような$ c_iの列について，$ \frac{N!}{c_1!c_2!\cdots c_M!} の総和を求める．

$ (1+x)(1+x+\frac{1}{2!}x^2)(1+x+\frac{1}{2!}x^2+\frac{1}{3!}x^3)\cdots の$ x^N の項が求めるものである．

あとはこれに従ってFFTすればいいし，何なら愚直に計算しても間に合う．